The system model of MIMO OFDM systems using NT transmit and NR receive antennas can be described in the frequency domain for every OFDM subcarrier individually by the received signal vector y=[y1, . . . , yNR]T, the NR×NT channel matrix H, the transmitted symbol x=[x1, . . . , xNT]T, and a disturbance vector n=[n1, . . . , nNR]T which represents the thermal noise on the receive antennas. The following equation then describes the transmission model:y=H·x+n  (1)
The elements of the transmitted symbol vector x are complex valued QAM symbols taken from a QAM modulation e.g. 4-QAM, 16-QAM, or 64-QAM. Depending on the modulation alphabet, every QAM symbol is associated to a number of transmitted bits NBit, with
      N    Bit    =      {                            2                                                    for              ⁢                                                          ⁢              4                        -            QAM                                                4                                                    for              ⁢                                                          ⁢              16                        -            QAM                                                6                                                    for              ⁢                                                          ⁢              64                        -            QAM                              
The elements of the channel matrix hi,j are also complex valued. They are estimated by the receiver.
At a certain stage of the signal processing chain the receiver computes softbits for every transmitted bit associated to the transmitted symbol vector x. Several methods are known for this purpose, with different error probabilities and different computational complexities. One near-optimal approach in terms of error probability is soft-decision sphere decoding.
A soft-decision sphere decoder takes the received signal vector y and the channel matrix H as input and outputs a softbit (i.e. a likelihood value) for every bit associated to x. When denoting the bits associated to xj (the QAM symbols of the j-th transmit antenna) by [bj,1, . . . , bj,n, . . . , bj,Nbit(j)], a softbit pj,n is defined by the following Euclidean distances:d0,j,n2=minx0,j,n{∥y−H·x0,j,n,∥2}d1,j,n2=minx1,j,n{∥y−H·x1,j,n∥2}  (2)wherein d0,j,n2 and d1,j,n2 are the minimum Euclidean distances between the received signal vector y and all possible combinations of transmit symbols x, with the restriction that x0,j,n represents all those combinations of x for which the n-th bit of the j-th transmit antenna is zero. On the other hand, x1,j,n represents all those combinations of x for which the n-th bit of the j-th transmit antenna is one. The softbit for the n-th bit of the j-th transmit antenna is given byρj,n=d02−d12  (3).
A straight-forward algorithm would have to consider all combinations of x in the above equations in order to compute the softbits for one OFDM subcarrier. Since this approach is computationally very intensive and implies an exponential complexity, soft-decision sphere decoding algorithms have been proposed as a way to simplify the search. The simplification is achieved by QR decomposition of the channel matrix H followed by a tree search.
QR decomposition decomposes the channel matrix H into a orthogonal rotation matrix Q and an upper triangular matrix R, such that H=Q·R. Since rotation by Q does not influence the Euclidean distances in the above equations, one can simplify the Euclidean distances d0,j,n2 and d1,j,n2 by
                                                        d                              0                ,                j                ,                n                            2                        =                                          min                                  x                                      0                    ,                    j                    ,                    n                                                              ⁢                              {                                                                                                                        y                        ′                                            -                                              R                        ·                                                  x                                                      0                            ,                            j                            ,                            n                                                                                                                                                    2                                }                                              ⁢                                          ⁢                      d                          1              ,              j              ,              n                        2                    =                                    min                              x                                  1                  ,                  j                  ,                  n                                                      ⁢                          {                                                                                                            y                      ′                                        -                                          R                      ·                                              x                                                  1                          ,                          j                          ,                          n                                                                                                                                      2                            }                                      ⁢                                  ⁢                              with            ⁢                                                  ⁢                          y              ′                                =                                    Q              H                        ·                          y              .                                                          (        4        )            
A second step of the sphere decoding algorithm is the tree search.
The Euclidean distance from above, d2=∥y′−R·x∥2, can be separated into partial Euclidean distances p12, . . . , pNT2 as follows:
                                              ⁢                                            d              2                        =                                                                                                                        (                                                                                                                                  y                              1                              ′                                                                                                                                                            …                                                                                                                                                              y                                                              N                                T                                                            ′                                                                                                                          )                                        -                                                                  (                                                                                                                                            r                                11                                                                                                                    …                                                                                                                      r                                                                  1                                  ⁢                                                                      N                                    T                                                                                                                                                                                                                                          0                                                                                      …                                                                                      …                                                                                                                                          0                                                                                      0                                                                                                                      r                                                                                                      N                                    T                                                                    ⁢                                                                      N                                    T                                                                                                                                                                                                      )                                            ⁢                                              (                                                                                                                                            x                                1                                                                                                                                                                        …                                                                                                                                                                          x                                                                  N                                  T                                                                                                                                                                    )                                                                                                              2                            =                                                p                  1                  2                                +                …                +                                  p                                      N                    T                                    2                                                              ,                                          ⁢                                          ⁢          with                                    (        5        )                                                          ⁢                              p                          N              T                        2                    =                                                                                    y                                      N                    T                                    ′                                -                                                      r                                                                  N                        T                                            ⁢                                              N                        T                                                                              ·                                      x                                          N                      T                                                                                                          2                                              (        6        )                                                          ⁢                              p            1            2                    =                                                                                                          y                    1                    ′                                    -                                                            r                      11                                        ·                                          x                      1                                                        -                  …                  -                                                            r                                              1                        ⁢                                                  N                          T                                                                                      ·                                          x                                              N                        T                                                                                                                        2                        .                                              (        7        )            
The partial Euclidean distances separate the original Euclidean distance into NT portions. Due to the upper triangular structure of the R matrix, the partial Euclidean distances also separate the distance computation from the possibly transmitted QAM symbols x1, . . . , xNT such that pNT2 only depends on the QAM symbol xNT and is not dependent on x1, . . . , xNT−1. Also, pNT−12 only depends on xNT and xNT−1, and is not dependent on x1, . . . , xNT−2. This kind of dependency separation is utilized by the sphere decoding tree search in order to find the “closest” possible transmit symbol vector xmin.
The sphere decoding tree search assumes a maximum Euclidean distance dmax2 which is definitely smaller than the Euclidean distance of the “closest” transmit symbol vector xmin. If now the search would start by choosing a candidate for xNT, the partial Euclidean distance pNT2 is determined. In case of pNT2>dmax2, all the Euclidean distances d2 for all possible combinations of x1, . . . , xNT−1 (assuming the chosen xNT) will also exceed the maximum search radius dmax2. Therefore, the search can skip computing the partial Euclidean distance p12, . . . , pNT−12, and can continue with another candidate for xNT.
This search procedure can be illustrated as a tree search as depicted in FIG. 1. The search tree consists of NT levels, that correspond to the QAM symbols of the different transmit antennas. In FIG. 1 NT=3 is assumed. Each tree node is associated to one possible QAM symbol x1, . . . , xNT. Therefore, the leave nodes of the tree represent all possible combinations of x.
In the example above, with pNT2>dmax2, after choosing a candidate for xNT the complete sub-tree below the chosen xNT would be skipped during the sphere search.
For finding the “closest” transmit symbol vector x, the maximum Euclidean distance dmax2 is initialized with ∞ (infinity). This means, that the partial Euclidean distances never exceed the limit, and that the sphere search reaches the bottom level after NT depth-first steps. The resulting Euclidean distance d2 then provides an update of the maximum search distance dmax2. The sphere search would now continue and try to update dmax2 if the bottom level of the tree is reached and if the resulting Euclidean distance would shrink dmax2.
The result of this search process is dmax2 being the Euclidean distance according to the “closest” possible symbol vector xmin. If xmin is restricted to certain bits being 0 or 1, the search tree can be adopted accordingly such that the search tree is built upon QAM symbols which meet the respective restrictions.
FIG. 2 illustrates an improvement of the sphere search by ordering the sibling nodes at a tree level k by increasing partial Euclidean distances pk2.
In a case where the maximum search distance dmax2 is exceeded at a tree level k (solid tree node) and the partial Euclidean distances pk2 are not ordered, the search would continue with the next candidate node (the respective QAM symbol xk) on the same level (arrow “A”). However, if the nodes in the tree are ordered by increasing pk2, the search can continue with the next node at level k−1 (arrow “B”). This is, permissible simply because due to the ordering of the sibling nodes the next candidate at the same level k would also exceed the maximum search distance dmax2. In this case, the sub-tree which is skipped during the sphere search is much larger, and thus search complexity is much lower. It will be understood from the above that ordering of the sibling nodes by increasing partial Euclidean distances is essential for any efficient sphere decoding algorithm.
As mentioned above, Euclidean distances have to be computed during the sphere decoding algorithm which are given by the following equation:d2=∥y′−R·x∥2  (8).
These distances are used as a search metric in order to find the closest possible symbol vector xmin and its associated Euclidean distance.
However, the computation of the Euclidean distances always requires multiplications for calculating the squared absolute value of a vector z=[z1, . . . , zNR] having complex elements zr.z=y′−R·x  (9)d2=∥z1∥2+ . . . +∥zNR∥2  (10)
For practical implementations multiplications always involve significant computational complexity. Furthermore, multiplications increase the bit-width requirements of the multiplication result.
An object of the invention therefore is to provide a sphere decoding search algorithm with reduced computational complexity.